package site.wanjiahao.graph;

import site.wanjiahao.heap.MinHeap;
import site.wanjiahao.union.GenericUnionFind;

import java.util.*;

public class ListGraph<V, E> extends AbstractGraph<V, E> {

    private Comparator<Edge<V, E>> comparator = (o1, o2) -> weightManager.compare(o1.weight, o2.weight);

    public ListGraph() {
    }

    public ListGraph(WeightManager<E> weightManager) {
        super(weightManager);
    }

    // 存储顶点集合
    Map<V, Vertex<V, E>> vertices = new HashMap<>();

    // 存储边集合
    Set<Edge<V, E>> edges = new HashSet<>();

    @Override
    public int edgeSize() {
        return edges.size();
    }

    @Override
    public int vertexSize() {
        return vertices.size();
    }

    @Override
    public void addEdge(V from, V to) {
        addEdge(from, to, null);
    }

    @Override
    public void addEdge(V from, V to, E weight) {
        // 如果顶点不存在
        Vertex<V, E> fromVertex = vertices.get(from);
        if (fromVertex == null) {
            fromVertex = new Vertex<>(from);
            vertices.put(from, fromVertex);
        }

        Vertex<V, E> toVertex = vertices.get(to);
        if (toVertex == null) {
            toVertex = new Vertex<>(to);
            vertices.put(to, toVertex);
        }

        // 直接覆盖原来的值
        Edge<V, E> edge = new Edge<>(fromVertex, toVertex, weight);
        edges.add(edge);
        // 添加顶点的出入边
        fromVertex.getOutEdge().add(edge);
        toVertex.getInEdge().add(edge);
    }

    @Override
    public void addVertex(V value) {
        if (vertices.containsKey(value)) return;
        vertices.put(value, new Vertex<>(value));
    }

    @Override
    public void removeEdge(V from, V to) {
        // 删除边
        Vertex<V, E> fromVertex = vertices.get(from);
        Vertex<V, E> toVertex = vertices.get(to);
        if (fromVertex == null || toVertex == null) return;

        Edge<V, E> edge = new Edge<>(fromVertex, toVertex);
        if (fromVertex.getOutEdge().remove(edge)) {
            toVertex.getInEdge().remove(edge);
            edges.remove(edge);
        }
    }

    @Override
    public void removeVertex(V value) {
        // 删除顶点，顶点对应的所有边移出
        Vertex<V, E> vertex = vertices.remove(value);
        if (vertex == null) return;

        // 删除入边，和出边
        Set<Edge<V, E>> inEdge = vertex.getInEdge();
        for (Edge<V, E> edge : inEdge) {
            Vertex<V, E> fromVertex = edge.from;
            // 删除from顶点，边集合的出边
            fromVertex.getOutEdge().remove(edge);
            edges.remove(edge);
        }

        Set<Edge<V, E>> outEdge = vertex.getOutEdge();
        for (Edge<V, E> edge : outEdge) {
            Vertex<V, E> toVertex = edge.to;
            // 删除to顶点，边集合的入边
            toVertex.getInEdge().remove(edge);
            edges.remove(edge);
        }
    }

    @Override
    public void bfs(V begin, Consumer consumer) {
        Vertex<V, E> vertex = vertices.get(begin);
        if (vertex == null) return;
        // 广度优先搜索，类似于二叉树的层序遍历
        LinkedList<Vertex<V, E>> queue = new LinkedList<>();
        // 存放已经遍历的元素
        Set<Vertex<V, E>> visitedEle = new HashSet<>();
        queue.offer(vertex);
        visitedEle.add(vertex);
        while (!queue.isEmpty()) {
            // 取出元素
            Vertex<V, E> veVertex = queue.poll();
            if (consumer.accept(veVertex.value)) return;

            for (Edge<V, E> edge : veVertex.getOutEdge()) {
                if (visitedEle.contains(edge.to)) continue;
                // 放入队列中
                queue.offer(edge.to);
                visitedEle.add(edge.to);
            }
        }
    }

    // 非递归实现
    @Override
    public void dfs(V begin, Consumer consumer) {
        // 非递归实现
        Vertex<V, E> vertex = vertices.get(begin);
        if (vertex == null) return;
        // 使用栈实现
        Stack<Vertex<V, E>> stack = new Stack<>();
        Set<Vertex<V, E>> visited = new HashSet<>();
        stack.push(vertex);
        visited.add(vertex);
        if (consumer.accept(vertex.value)) return;
        while (!stack.isEmpty()) {
            Vertex<V, E> veVertex = stack.pop();
            for (Edge<V, E> edge : veVertex.getOutEdge()) {
                if (visited.contains(edge.to)) continue;
                stack.push(edge.from);
                stack.push(edge.to);
                visited.add(edge.to);
                if (consumer.accept(edge.to.value)) return;
                break;
            }
        }

    }

    @Override
    public List<V> topologicSort() {
        // 拓扑排序，找到其中入度为0的节点，循环执行此过程，使用ins记录入边的数量
        ArrayList<V> list = new ArrayList<>();
        LinkedList<Vertex<V, E>> queue = new LinkedList<>();
        // 入边计数集合
        HashMap<Vertex<V, E>, Integer> ins = new HashMap<>();
        vertices.forEach((v, vertex) -> {
            int size = vertex.getInEdge().size();
            if (size == 0) {
                // 存入队列中
                queue.offer(vertex);
            } else {
                // 存放入入边计数集合
                ins.put(vertex, size);
            }
        });
        // 遍历队列元素
        while (!queue.isEmpty()) {
            Vertex<V, E> vertex = queue.poll();
            list.add(vertex.value);
            Set<Edge<V, E>> outEdge = vertex.getOutEdge();
            for (Edge<V, E> edge : outEdge) {
                int size = ins.get(edge.to) - 1;
                if (size == 0) {
                    queue.offer(edge.to);
                } else {
                    ins.put(edge.to, size);
                }
            }
        }
        return list;
    }

    // 最小生成树
    @Override
    public Set<EdgeInfo<V, E>> mst() {
        return Math.random() < 0.5 ? prim() : kruskal();
    }

    // 最短路径
    @Override
    public Map<V, PathInfo<V, E>> shortestPath(V begin) {
        return bellmanFord(begin);
    }

    // 多源最短路径
    @Override
    public Map<V, Map<V, PathInfo<V, E>>> shortestPath() {
        Map<V, Map<V, PathInfo<V, E>>> paths = new HashMap<>();
        // 初始化数据
        for (Edge<V, E> edge : edges) {
            V from = edge.from.value;
            Map<V, PathInfo<V, E>> map = paths.computeIfAbsent(from, k -> new HashMap<>());
            // 添加to数据
            V to = edge.to.value;
            PathInfo<V, E> pathInfo = new PathInfo<>(edge.weight);
            pathInfo.getEdgeInfos().add(edge.toEdgeInfo());
            map.put(to, pathInfo);
        }
        // O(v^3)
        vertices.forEach((v2, vertex2) -> {
            vertices.forEach((v1, vertex1) -> {
                vertices.forEach((v3, vertex3) -> {
                    if (v1.equals(v2) || v1.equals(v3) || v2.equals(v3)) return;

                    // 获取path12路径
                    PathInfo<V, E> path12 = getPath(paths, v1, v2);
                    if (path12 == null) return;

                    // 获取path23路径
                    PathInfo<V, E> path23 = getPath(paths, v2, v3);
                    if (path23 == null) return;

                    // 获取path13路径
                    PathInfo<V, E> path13 = getPath(paths, v1, v3);
                    E newWeight = weightManager.add(path12.getWeight(), path23.getWeight());
                    if (path13 != null && weightManager.compare(newWeight, path13.getWeight()) >= 0)return;

                    if (path13 == null) {
                        path13 = new PathInfo<V, E>(weightManager.zero());
                        paths.get(v1).put(v3, path13);
                    } else {
                        path13.getEdgeInfos().clear();
                    }

                    path13.setWeight(newWeight);
                    path13.getEdgeInfos().addAll(path12.getEdgeInfos());
                    path13.getEdgeInfos().addAll(path23.getEdgeInfos());
                });
            });
        });
        return paths;
    }

    private PathInfo<V, E> getPath(Map<V, Map<V, PathInfo<V, E>>> paths, V v1, V v2) {
        Map<V, PathInfo<V, E>> v1Path = paths.get(v1);
        if (v1Path == null) return null;
        return v1Path.get(v2);
    }


    // 迪杰斯特拉
    private Map<V, PathInfo<V, E>> dijkstra(V begin) {
        // 未发生hash冲突 可以认为O（1），发生hash冲突 （n个元素）链表O (N) 红黑树logn
        Vertex<V, E> beginVertex = vertices.get(begin);
        if (beginVertex == null) return null;
        Map<V, PathInfo<V, E>> selectedPaths = new HashMap<>();
        HashMap<Vertex<V, E>, PathInfo<V, E>> paths = new HashMap<>();
        // 从paths中选出最小的集合
        // O(1)
        paths.put(beginVertex, new PathInfo<>(weightManager.zero()));
        // V
        while (!paths.isEmpty()) {
            // 取出最小的路径
            Map.Entry<Vertex<V, E>, PathInfo<V, E>> minPath = getMinPath(paths);
            Vertex<V, E> minKey = minPath.getKey();
            PathInfo<V, E> minValue = minPath.getValue();
            selectedPaths.put(minKey.value, minValue);
            paths.remove(minKey);
            for (Edge<V, E> edge : minKey.getOutEdge()) {
                // 路径已经被选中
                if (selectedPaths.containsKey(edge.to.value)) continue;
                relaxDijkstra(paths, minValue, edge);
            }

        }
        selectedPaths.remove(begin);
        return selectedPaths;
    }

    //
    private Map<V, PathInfo<V, E>> bellmanFord(V begin) {
        Vertex<V, E> beginVertex = vertices.get(begin);
        if (beginVertex == null) return null;
        Map<V, PathInfo<V, E>> selectedPaths = new HashMap<>();
        selectedPaths.put(begin, new PathInfo<>(weightManager.zero()));
        int count = vertices.size() - 1;
        for (int i = 0; i < count; i++) {
            // 对所有边进行n - 1次松弛后，必定找出最短路径
            for (Edge<V, E> edge : edges) {
                PathInfo<V, E> minPath = selectedPaths.get(edge.from.value);
                if (minPath == null) continue;
                relaxBellmanFord(selectedPaths, minPath, edge);
            }
        }

        // 再次进行松弛操作后，还有最小值，值说明存在负权环
        for (Edge<V, E> edge : edges) {
            PathInfo<V, E> minPath = selectedPaths.get(edge.from.value);
            if (minPath == null) continue;
            if (relaxBellmanFord(selectedPaths, minPath, edge)) {
                System.out.println("有负权环");
                return null;
            }
        }

        selectedPaths.remove(begin);
        return selectedPaths;
    }

    private void relaxDijkstra(Map<Vertex<V, E>, PathInfo<V, E>> paths, PathInfo<V, E> minValue, Edge<V, E> edge) {
        // 进行路径松弛操作, 可能获取到的数据为空
        PathInfo<V, E> oldPathInfo = paths.get(edge.to);
        if (oldPathInfo == null) {
            oldPathInfo = new PathInfo<>(weightManager.max());
            paths.put(edge.to, oldPathInfo);
        }
        E newWeight = weightManager.add(minValue.getWeight(), edge.weight);
        if (weightManager.compare(oldPathInfo.getWeight(), newWeight) > 0) {
            // weight信息改变
            oldPathInfo.setWeight(newWeight);
            // 路径信息改变
            oldPathInfo.getEdgeInfos().clear();
            oldPathInfo.getEdgeInfos().addAll(minValue.getEdgeInfos());
            oldPathInfo.getEdgeInfos().add(edge.toEdgeInfo());
        }
    }

    private boolean relaxBellmanFord(Map<V, PathInfo<V, E>> paths, PathInfo<V, E> minValue, Edge<V, E> edge) {
        // 进行路径松弛操作, 可能获取到的数据为空
        PathInfo<V, E> oldPathInfo = paths.get(edge.to.value);
        if (oldPathInfo == null) {
            oldPathInfo = new PathInfo<>(weightManager.max());
            paths.put(edge.to.value, oldPathInfo);
        }
        E newWeight = weightManager.add(minValue.getWeight(), edge.weight);
        if (oldPathInfo != null && weightManager.compare(oldPathInfo.getWeight(), newWeight) > 0) {
            // weight信息改变
            oldPathInfo.setWeight(newWeight);
            // 路径信息改变
            oldPathInfo.getEdgeInfos().clear();
            oldPathInfo.getEdgeInfos().addAll(minValue.getEdgeInfos());
            oldPathInfo.getEdgeInfos().add(edge.toEdgeInfo());
            return true;
        } else {
            return false;
        }
    }

    // 遍历选出最小的边
    private Map.Entry<Vertex<V, E>, PathInfo<V, E>> getMinPath(HashMap<Vertex<V, E>, PathInfo<V, E>> paths) {
        Set<Map.Entry<Vertex<V, E>, PathInfo<V, E>>> entries = paths.entrySet();
        Iterator<Map.Entry<Vertex<V, E>, PathInfo<V, E>>> iterator = entries.iterator();
        Map.Entry<Vertex<V, E>, PathInfo<V, E>> minEntry = iterator.next();
        while (iterator.hasNext()) {
            Map.Entry<Vertex<V, E>, PathInfo<V, E>> cur = iterator.next();
            if (weightManager.compare(minEntry.getValue().getWeight(), cur.getValue().getWeight()) > 0) {
                minEntry = cur;
            }
        }
        return minEntry;
    }

    public Set<EdgeInfo<V, E>> prim() {
        int size = vertices.size();
        if (size < 1) return null;
        // 取出第一个元素
        HashSet<EdgeInfo<V, E>> edges = new HashSet<>();
        Iterator<Vertex<V, E>> it = vertices.values().iterator();
        Set<Vertex<V, E>> addVertex = new HashSet<>();
        Vertex<V, E> first = it.next();
        addVertex.add(first);
        // 找到当前元素的最小边，可以使用二叉堆来做
        MinHeap<Edge<V, E>> minHeap = new MinHeap(first.outEdge, comparator);
        while (!minHeap.isEmpty() && addVertex.size() < size) {
            // 获取最小边
            Edge<V, E> edge = minHeap.remove();
            if (addVertex.contains(edge.to)) continue;
            // 加入边集合
            edges.add(edge.toEdgeInfo());
            addVertex.add(edge.to);
            // 再次选出最小边，需要注意的是，添加过的顶点可能会再次出现
            minHeap.addAll(edge.to.outEdge);
        }
        return edges;
    }

    // 克鲁斯卡尔算法， 边集从大到小选，如果选中的边会构成环路，至不加入边集
    // 构成环路算法，可以使用并查集，如果边的from，to的父节点相同则会构成环
    public Set<EdgeInfo<V, E>> kruskal() {
        int size = vertices.size() - 1;
        if (size < 0) return null;
        HashSet<EdgeInfo<V, E>> addEdges = new HashSet<>();
        // 边集存放入最小堆
        MinHeap<Edge<V, E>> minHeap = new MinHeap<>(edges, comparator);
        // 顶点放入并查集中
        GenericUnionFind<Vertex<V, E>> unionFind = new GenericUnionFind<>();
        vertices.forEach(((v, vertex) -> {
            unionFind.makeSet(vertex);
        }));
        while (!minHeap.isEmpty() && addEdges.size() < size) {
            Edge<V, E> edge = minHeap.remove();
            if (unionFind.isSame(edge.from, edge.to)) continue;
            addEdges.add(edge.toEdgeInfo());
            // 合并
            unionFind.union(edge.from, edge.to);
        }
        return addEdges;
    }

    // 递归实现
    public void recursionDfs(V begin, Consumer consumer) {
        // 图的深度遍历，类似于二叉树的前序遍历
        Vertex<V, E> vertex = vertices.get(begin);
        if (vertex == null) return;
        dfs(vertex, consumer, new HashSet<>());
    }


    private void dfs(Vertex<V, E> vertex, Consumer consumer, Set<Vertex<V, E>> visited) {
        if (consumer.isStop) return;
        // 遍历当前节点
        consumer.isStop = consumer.accept(vertex.value);
        visited.add(vertex);
        // 获取到出度节点
        Set<Edge<V, E>> outEdge = vertex.getOutEdge();
        for (Edge<V, E> edge : outEdge) {
            // 递归遍历，判断当前节点是否被遍历过
            if (visited.contains(edge.to)) continue;
            dfs(edge.to, consumer, visited);
        }
    }

    public void print() {
        System.out.println("[顶点]-------------------");
        vertices.forEach((V v, Vertex<V, E> vertex) -> {
            System.out.println(v);
            System.out.println("out-----------");
            System.out.println(vertex.getOutEdge());
            System.out.println("in-----------");
            System.out.println(vertex.getInEdge());
        });

        System.out.println("[边]-------------------");
        edges.forEach(System.out::println);
    }

    // 定义顶点
    private static class Vertex<V, E> {
        V value;

        // 无顺序之分，最后使用set
        Set<Edge<V, E>> inEdge;

        Set<Edge<V, E>> outEdge;

        public Set<Edge<V, E>> getInEdge() {
            if (inEdge == null) {
                inEdge = new HashSet<>();
            }
            return inEdge;
        }

        public Set<Edge<V, E>> getOutEdge() {
            if (outEdge == null) {
                outEdge = new HashSet<>();
            }
            return outEdge;
        }

        public Vertex(V value) {
            this.value = value;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Vertex<?, ?> vertex = (Vertex<?, ?>) o;
            return Objects.equals(value, vertex.value);
        }

        @Override
        public int hashCode() {
            return value.hashCode();
        }
    }

    // 边定义
    private static class Edge<V, E> {
        Vertex<V, E> from;

        Vertex<V, E> to;

        E weight;

        public Edge(Vertex<V, E> form, Vertex<V, E> to) {
            this.from = form;
            this.to = to;
        }

        public Edge(Vertex<V, E> form, Vertex<V, E> to, E weight) {
            this.from = form;
            this.to = to;
            this.weight = weight;
        }

        private EdgeInfo<V, E> toEdgeInfo() {
            return new EdgeInfo<V, E>(from.value, to.value, weight);
        }

        // 必须实现equals，和hashcode

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Edge<?, ?> edge = (Edge<?, ?>) o;
            return from.equals(edge.from) && to.equals(edge.to);
        }

        @Override
        public int hashCode() {
            return Objects.hash(from, to);
        }

        @Override
        public String toString() {
            final StringBuilder sb = new StringBuilder("Edge{");
            sb.append("from=").append(from.value);
            sb.append(", to=").append(to.value);
            sb.append(", weight=").append(weight);
            sb.append('}');
            return sb.toString();
        }
    }

}
